import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-02-01
 * Time: 22:06
 * <p>
 * https://www.nowcoder.com/share/jump/7745334641706796444150
 */


public class BM95 {

    public int candy(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 连续上升的坡度
        int up = 0;
        // 连续下降的坡度
        int down = 0;
        // 峰顶的糖果数
        int peak = 1;
        // 返回值
        int res = 1;
        // 遍历数组
        for (int i = 1; i < arr.length; i++) {
            // 相当于每个位置的糖果数初始化为 1
            res++;
            // 1. 坡度上升
            if (arr[i] > arr[i - 1]) {
                // 更新当前位置的坡度
                up++;
                down = 0;
                // 加上当前位置的糖果数（即坡度）
                res += up;
                // 更新峰顶的糖果数
                peak = up + 1;
            } else if (arr[i] == arr[i - 1]) {// 2. 没有坡
                up = down = 0;
                peak = 1;
            } else { // 3. 坡度下降
                up = 0;
                res += down;
                down++;
                if (down >= peak) { // 下降的高度大于上升的高度，需要额外考虑峰值的糖果数
                    res++;
                }
            }
        }
        return res;
    }
}


class BM95_2 {

    public int candy(int[] arr) {
        // 判断空
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 1. 开辟数组记录结果
        int n = arr.length;
        int[] result = new int[n];
        // 初始化每个位置都为 1 个糖果
        Arrays.fill(result, 1);
        // 2. 从左到右遍历数组，如果是连续递增的元素，就累加
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                result[i] = result[i - 1] + 1;
            }
        }
        // 3. 再次从右向左遍历，如果是连续递增的元素且糖果数更小，就累加
        // 记录糖果总数
        int res = result[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1] && result[i] <= result[i + 1]) {
                result[i] = result[i + 1] + 1;
            }
            // 累加糖果总数
            res += result[i];
        }
        return res;
    }
}